package 回溯;

import org.junit.Assert;
import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @description: 未解决
 * @author: shuai.chen@shuyun.com
 * @date: 2023/2/8 10:44 AM
 */
public class EightQueen3 {

    List<List<String>> resList = new ArrayList<>();

    @Test
    public void test2(){
        solveNQueens(8);
        Assert.assertSame(92, resList.size());
    }

    private void solveNQueens(int n) {
        int[][] attack = new int[n][n];
        // List<List<Integer>> attack = new ArrayList<>();
        char[][] queue = new char[n][n];
        init(attack, queue);
        dfs(0, attack, queue);
    }

    /**
     *
     * @param row 当前行, 从0开始
     * @param attack
     * @param queue
     */
    private void dfs(int row, int[][] attack, char[][] queue) {
        // 结束
        if (row == attack.length) {
            List<String> list = new ArrayList<>();
            for (int i = 0; i < attack.length; i++) {
                list.add(new String(queue[i]));
            }
            resList.add(list);
            return;
        }
        for (int col = 0; col < attack.length; col++) {
            if (attack[row][col] == 0) {
                int[][] tempAttack = Arrays.copyOf(attack, attack.length);
                // 更新 queue
                queue[row][col] = 'Q';
                // 更新 attack
                updateAttack(row, col, attack);

                // 递归 row+1
                dfs(row + 1, attack, queue);

                // 恢复 queue
                queue[row][col] = '*';
                // 恢复 attack
                attack = Arrays.copyOf(tempAttack, tempAttack.length);
            }
        }
    }

    private void updateAttack(int row, int col, int[][] attack) {
        attack[row][col] = 1;

        /*
             (-1,-1)  (-1,0)  (-1,1)
             (0,-1)   (row,col)   (0,1)
             (1,-1)   (1,0)   (1,1)
         */

        // 竖 、 横  、 左上右上 、 左下右下
        int[] dx = {-1, 1, 0, 0, -1, -1, 1, 1};
        int[] dy = {0, 0, -1, 1, -1, 1, -1, 1};

        // (row,col) 向外扩散 1 到 n-1 个距离
        for (int i = 1; i < attack.length; i++) {
            for (int j = 0; j < attack.length; j++) {
                int newRow = row + i * dx[j];
                int newCol = col + i * dy[j];
                // 在棋盘内
                if (newRow >= 0 && newRow < attack.length
                        && newCol >= 0 && newCol < attack.length) {
                    attack[newRow][newCol] = 1;
                }
            }
        }
    }

    private void init(int[][] attack, char[][] queue) {
        for (int i = 0; i < attack.length; i++) {
            for (int j = 0; j < attack.length; j++) {
                attack[i][j] = 0;
                queue[i][j] = '*';
            }
        }
    }


    @Test
    public void test02(){
        int[] a = new int[4];
        int[] temp = Arrays.copyOf(a, a.length);
        a[2] = 2;
        System.out.println(Arrays.toString(temp));
    }

}

